package io.adrainty.algorithm.leetcode.normal;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author adrainty
 * @version v1.0.0
 * @since 2024/12/27 上午10:42
 */
public class Solution139 {

    private static final Map<String, Boolean> map = new HashMap<>();

    public boolean wordBreak(String s, List<String> wordDict) {
        if (map.containsKey(s)) {
            return map.get(s);
        }
        for (String word : wordDict) {
            if (word.equals(s)) {
                map.put(s, true);
                return true;
            }
            if (s.startsWith(word)) {
                String sub = s.substring(word.length());
                if (wordBreak(sub, wordDict)) {
                    map.put(sub, true);
                    return true;
                }
            }
        }
        map.put(s, false);
        return false;
    }

    public static void main(String[] args) {
        System.out.println(new Solution139().wordBreak("a", List.of("b")));
    }
}
